package graph;

import java.util.ArrayList;

public class GraphByNode {
    static class Node{
        public int src;//起始位置
        public int dest;//目标位置
        public int weight;//权重
        public Node next;

        public Node(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public ArrayList<Node> edgeList;//邻接表
    public boolean isDirect;//是否为有向图
    public char[] arrayV;//顶点数组

    //构造方法
    //注意ArrayList 的处理，如果不赋 null, ArrayList 的有效数据为 0， 无法进行访问的
    public GraphByNode(int size, boolean isDirect) {
        this.edgeList = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            edgeList.add(null);
        }
        this.isDirect = isDirect;
        this.arrayV = new char[size];
    }

    //初始化顶点数组
    public void initArrayV(char[] arrayV) {
        for (int i = 0; i < arrayV.length; i++) {
            this.arrayV[i] = arrayV[i];
        }
    }

    //添加边
    public void addEdge(char src, char dest, int weight) {
        int indexSrc = getIndexOfV(src);
        int indexDest = getIndexOfV(dest);

        addNode(indexSrc,indexDest,weight);

        //无向图，再次添加
        if(!isDirect) {
            addNode(indexDest,indexSrc,weight);
        }
    }

    private void addNode(int indexSrc, int indexDest, int weight) {
        //首先判断这个节点是否存在
        Node cur = edgeList.get(indexSrc);
        while(cur != null) {
            if(cur.dest == indexDest) {
                return;
            }
            cur = cur.next;
        }

        //没有存储，进行存储
        Node newNode = new Node(indexSrc,indexDest,weight);
        newNode.next = edgeList.get(indexSrc);
        edgeList.set(indexSrc,newNode);
    }

    //获取下标
    private int getIndexOfV(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if(arrayV[i] == v) {
                return i;
            }
        }
        return -1;
    }

    //获取度
    public int getDegreeOfV(char v) {
        int count = 0;
        int index = getIndexOfV(v);
        Node cur = edgeList.get(index);
        while(cur != null) {
            count++;
            cur = cur.next;
        }

        //有向图，单独处理入度
        if(isDirect) {
            for (int i = 0; i < arrayV.length; i++) {
                if (i != index) {
                    cur = edgeList.get(i);
                    while (cur != null) {
                        if (cur.dest == index) {
                            count++;
                        }
                        cur = cur.next;
                    }
                }
            }
        }
        return count;
    }

    //打印邻接表
    public void printGraph() {
        for (int i = 0; i < arrayV.length; i++) {
            Node cur = edgeList.get(i);
            while(cur != null) {
                System.out.print(cur.dest + ":" + cur.weight + "-> ");
                cur = cur.next;
            }
            System.out.println();
        }
    }

}
